package tree.test117;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/17 9:36
 */
public class Solution1 {

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    public Node connect(Node root) {
        if (root == null) return root;
        Node pre = root;
        Node cur = null;
        while (true) {
            cur = pre;
            while (cur != null) {
                //首先如果当前节点无孩子，则直接跳到cur节点的next节点上面
                if (cur.left == null && cur.right == null) {
                    cur = cur.next;
                    continue;
                }
                //否则的话当前节点至少有一个孩子
                Node next = cur.next;
                while (next != null && next.left == null && next.right == null) {
                    next = next.next;
                    if (next == null) {
                        break;
                    }
                }
                //当前节点的左右孩子都不为空，就将 left.next 指向 right
                if (cur.left != null && cur.right != null) {
                    cur.left.next = cur.right;
                }
                //要接上 next 的节点的孩子，所以用 temp 处理当前节点 right 为 null 的情况
                Node temp = cur.right == null ? cur.left : cur.right;

                if (next != null) {
                    //next 左孩子不为 null，就接上左孩子。
                    if (next.left != null) {
                        temp.next = next.left;
                        //next 左孩子为 null，就接上右孩子。
                    } else {
                        temp.next = next.right;
                    }
                }

                cur = cur.next;
            }
            //跳出上一个循环之后则表示当前层已经全部遍历完成了，将pre拿回来找出当前初始节点pre拥有孩子的节点
            while (pre.left == null && pre.right == null) {
                pre = pre.next;
                //都没有孩子说明已经是最后一层了
                if (pre == null) {
                    return root;
                }
            }
            //进入下一层
            pre = pre.left != null ? pre.left : pre.right;
        }
    }
}
